package algorithms.leaning.class12;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * 给定一棵二叉树的头节点head，返回这颗二叉树是不是满二叉树
 * 任何一颗高度为 n 的树的节点个数为 2^n -1
 *
 * @author guichang
 * @date 2021/6/12
 */

@SuppressWarnings("all")
public class Code5_二叉树_满二叉树 {

    public static void main(String[] args) {
        MyUtil.print(isBFT(MyUtil.createTreeNode(1, 2, 3)));
        MyUtil.print(isBFT(MyUtil.createTreeNode(1, 2, 3, 4, 5)));
        MyUtil.print(isBFT(MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7)));
    }

    public static boolean isBFT(TreeNode head) {
        return process(head).bft;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(true, 0);
        }
        Info tl = process(node.left);
        Info tr = process(node.right);
        boolean isFBT = tl.bft && tr.bft && (tl.height - tr.height == 0);
        int height = Math.max(tl.height, tr.height) + 1;
        return new Info(isFBT, height);
    }

    private static class Info {
        boolean bft; // 是否满二叉树
        int height; // 树高度

        public Info(boolean isFBT, int height) {
            this.bft = isFBT;
            this.height = height;
        }
    }
}